package leetcode.editor.cn;

import java.util.List;

//[120]三角形最小路径和
public class Triangle120{
public static void main(String[] args) {
   Solution solution = new Triangle120().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //状态的定义 ：每个位置，从下到上的最优解
        // 状态转移方程 局部最优，f[n-1,i] = min(f[n,i] ,f[n ,i+1]) +f[n-1,i];
        if (triangle == null || triangle.size()<1 || triangle.get(triangle.size()-1).size()<1)return 0;
        int colSize = triangle.get(triangle.size() - 1).size();

//        //初始化 缓存 数组。存放每个位置最小值。
//        int cache [][] = new int[triangle.size()][colSize];
//
//        //从下->上，算出每一个位置的最小值。
//        for (int i = triangle.size()-1; i>=0; i--) {
//            for (int j = 0; j < triangle.get(i).size(); j++) {
//                Integer num = triangle.get(i).get(j);
//                if (i == triangle.size()-1){
//                    cache[i][j] = num;
//                }else {
//                    int a = cache[i + 1][j];
//                    int b = cache[i + 1][j+1];
//                    cache[i][j] = (a<b ? a : b) + num;
//                }
//
//            }
//        }
//        return cache[0][0];

        //优化 缓存 按层遍历，只需要最长1层就好。
        //没有使用原有的数据空间，作为缓存。没有修改覆盖，原有的数据。
        int cache [] = new int[colSize]; //【cache 只需要 1 层】【cache 只需要 1 层】【cache 只需要 1 层】

        //从下->上，算出每一个位置的最小值。
        for (int i = triangle.size()-1; i>=0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                Integer num = triangle.get(i).get(j);
                if (i == triangle.size()-1){
                    cache[j] = num;
                }else {
                    int a = cache[j];//下面一层的缓存的值。
                    int b = cache[j+1];
                    cache[j] = (a < b ? a : b) + num;
                }

            }
        }
        return cache[0];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}